import com.kiwi.nixu.common.LNode;
import com.sun.xml.internal.ws.handler.HandlerException;

import javax.sql.rowset.FilteredRowSet;
import java.io.FileReader;

/**
 * 题目描述：
 * 单链表有环指的是单链表中某个结点的next域指向链表中在它之前的某一个结点，
 * 这样在链表的尾部形成一个环形结构。如何判断单链表是否有环存在？
 */
public class F如何检测一个较大的单链表是否又环 {

    /**
     * 方法一：
     * 蛮力法定义一个HashSet 用来存放结点的引用，并将其初始化为空，
     * 从链表的头结点开始向后遍历，每遍历到一个结点就判断HashSet中是否有这个结点的引用。
     * 如果没有，说明这个结点是第一次访问，还没有形成环，那么将这个结点的引用添加到HashSet中去。
     * 如果在HashSet中找到了同样的结点，那么说明这个结点已经被访问过了，于是就形成了环。
     * 这种方法的时间复杂度为O（N），空间复杂度也为O（N）
     * <p>
     * 方法二：
     * 快慢指针遍历法定义两个指针fast（快）与slow（慢），两者的初始值都指向链表头，
     * 指针slow每次前进一步，指针fast每次前进两步。
     * 两个指针同时向前移动，快指针每移动一次都要跟慢指针比较，
     * 如果快指针等于慢指针，就证明这个链表是带环的单向链表，
     * 否则证明这个链表是不带环的循环链表。实现代码见后面引申部分
     */

    private static class 如果链表存在有环那么如何找出环的入口点 {

        /**
         * 分析与解答：
         * 当链表有环时，如果知道环的入口点，那么在需要遍历链表或释放链表所占的空间时方法将会非常简单，
         * 下面主要介绍查找链表环入口点的思路。
         * 如果单链表有环，那么按照上述方法二的思路，
         * 当走得快的指针fast与走得慢的指针slow相遇时，
         * slow指针肯定没有遍历完链表，而fast指针已经在环内循环了n圈（1≤n）。
         * 如果slow指针走了s步，则fast指针走了2s步（fast步数还等于s 加上在环上多转的n圈），
         * 假设环长为r，则满足如下关系表达式：[插图]
         * 由此可以得到：s=nr设整个链表长为L，
         * 入口环与相遇点距离为x，起点到环入口点的距离为a。
         * 则满足如下关系表达式：[插图]（L-a-x）为相遇点到环入口点的距离，
         * 从链表头到环入口点的距离=（n-1）*环长+相遇点到环入口点的长度，
         * 于是从链表头与相遇点分别设一个指针，
         * 每次各走一步，两个指针必定相遇，且相遇的第一点为环入口点
         */

        public static LNode constructList() {
            int i = 1;
            LNode head = new LNode();
            head.next = null;
            LNode tmp = null;
            LNode cur = head;
            for (; i < 8; i++) {
                tmp = new LNode();
                tmp.data = i;
                tmp.next = null;
                cur.next = tmp;
                cur = tmp;
            }
            cur.next = head.next.next.next;
            return head;
        }

        public static LNode isLoop(LNode head) {
            if (head == null || head.next == null) {
                return null;
            }
            //初始slow与fast都指向链表第一个节点
            LNode slow = head.next;
            LNode fast = head.next;
            while (fast != null && fast.next != null) {
                System.out.println("slow:" + slow.data + ",fast:" + fast.data);
                slow = slow.next;
                fast = fast.next.next;
                if (slow == fast) {
                    return slow;
                }
            }
            return null;
        }

        public static LNode findLoopNode(LNode head, LNode meetNode) {
            LNode first = head.next;
            LNode second = meetNode;
            while (first != second) {
                first = first.next;
                second = second.next;
            }
            return first;
        }

        /**
         * 示例代码中给出的链表为1→2→3→4→5→6→7→3（3实际代表链表第三个结点）。
         * 因此， isLoop函数返回的结果为两个指针相遇的结点，
         * 所以链表有环，通过函数FindLoopNode可以获取到环的入口点为3
         *
         * @param args
         */
        public static void main(String[] args) {
            LNode head = constructList();
            LNode meetNode = isLoop(head);
            LNode loopNode = null;
            if (meetNode != null) {
                System.out.println("有环");
                loopNode = findLoopNode(head, meetNode);
                System.out.println("环的入口点为：" + loopNode.data);
            } else {
                System.out.println("无环");
            }
        }
    }
}
